package leetcode;

public class PalindromeLinkedList234 {
    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            ListNode pointer = this;
            StringBuilder sb = new StringBuilder();
            sb.append("{");
            while (pointer != null) {
                sb.append(pointer.val);
                if (pointer.next != null) {
                    sb.append(",");
                }
                pointer = pointer.next;
            }
            sb.append("}");
            return sb.toString();
        }
    }

    // 找到中间点 快慢指针法
    public ListNode getMid(ListNode head) {
        ListNode p1 = head;
        ListNode p2 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }

    // 取反 面向过程取反
    public ListNode reverse(ListNode middle) { // 这个中间点 取反并未改变head.next指向 所以有两个指向他
        ListNode n1 = null;
        ListNode o2;
        while (middle != null) {
            o2 = middle.next;
            middle.next = n1;
            n1 = middle;
            middle = o2;
        }
        return n1;
    }

    // 对比
    public boolean isPalindrome(ListNode head) {
        ListNode middle = getMid(head);
        ListNode reversed = reverse(middle);
        System.out.println(head);
        System.out.println(reversed);
        while (reversed != null) {
            if (head.val != reversed.val) {
                return false;
            }
            head = head.next;
            reversed = reversed.next;
        }
        return true;
    }

    // 优化时间 找中间节点的同时反转前半部链表 在进行比较
    public boolean isPalindrome2(ListNode head) {
        ListNode p1 = head;
        ListNode p2 = head;
        ListNode n1 = null;
        ListNode o1 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            o1.next = n1;
            n1 = o1;
            o1 = p1;
        }
        if (p2 != null) {  // 偶数指针p2为null 奇数不为null
            p1 = p1.next;
        }
        while (n1 != null) {
            if (p1.val != n1.val) {
                return false;
            }
            n1 = n1.next; // 比较 指针要往后移 别忘了
            p1 = p1.next;
        }
        return true;
    }
}
